//解法3：动态规划——优化空间复杂度O(1)
//时间复杂度：O（N）
#include<iostream>
using namespace std;
class Solution
{
public:
	int Fibonacci(int n)
	{
		if (n == 0)
			return 0;
		if (n == 1)
			return 1;
		int fn;
		int fn1 = 1;
		int fn2 = 0;

		//状态初始化 fn1 fn2
		//状态转移方程：fn=fn1+fn2;
		for (int i = 2; i <= n; i++)
		{
			fn = fn1 + fn2;
			//更新中间状态
			fn2 = fn1;
			fn1 = fn;
		}
		val= fn;
		return val;
	}
	void Print()const
	{
		cout << val << endl;
	}
private:
	size_t val;
};
int main()
{
	Solution fib;
	fib.Fibonacci(45);
	fib.Print();
	return 0;
}
